#ifndef __ConjString_H__
#define __ConjString_H__

#include <iostream>
#include <cassert>
#include "String.h"

using namespace std;


struct NodoConjString {

	String elemento;
	NodoConjString *siguiente;

};

struct NodoTrie {

	NodoTrie* hijos[27];
	bool fin;

};

int char2nat( char ch ) {
	
	return ch - 97;
}

bool hayMasRamas (const NodoTrie &n, int i) {
	int i2 = 0;
	bool retorno = false;
	while (i2 < 27 && !retorno) {
		if (i2 != i)
			retorno = (n.hijos[i2] != NULL);
		i2++;
	}
	return retorno;
}

bool esUnaHoja(const NodoTrie &n) {

	int i = 0;
	bool retorno = true;
	while ( i < 27 && retorno) {
		if (n.hijos[i] != NULL) {
			retorno = false;
		}
		i++;
	}
	return retorno;
}

void borrarRama(NodoTrie ** &n) {


	NodoTrie *aux;
	aux = *n;
	int i = 0;
	while (i != 27) {

		i = 0;
		while ((*n) -> hijos[i] == NULL && i != 27) {
			i++;
		}
		if (i != 27) {
			*n = (*n) -> hijos[i];
			delete aux;
			aux = *n;
		}

	}
	aux = *n;
	delete aux;
	*n = NULL;
}

class ConjString
{

	friend class IteradorConjString;
	public:

		// el constructor crea el ConjString vacio
		ConjString();


		// Crea un ConjString como copia de otro. 
		ConjString(const ConjString &otro);

		// Destructor
		~ConjString();

		void agregar(String &s);

		void eliminar(const String &s);

		bool pertenece(const String &s);

		int dameTamano();

		bool vacio();

		ConjString &operator=(const ConjString &otro); 

		bool operator==(const ConjString &otro) const; 

		bool operator!=(const ConjString &otro) const; 

		// Imprime el ConjString en pantalla en forma legible.
		friend ostream & operator<<(ostream &o, const ConjString &esp);


	private:

		int tamano;
		NodoConjString *listaEnlazada;
		NodoTrie *trie;

	
};

ConjString::ConjString() {
	
	tamano = 0;
	listaEnlazada = NULL;
	trie = NULL;


}


ConjString::~ConjString() {
	NodoConjString *p;
	String aux;
	p = listaEnlazada;
	while ( ! (p == NULL) ) {
		aux = p -> elemento;
		p = (p -> siguiente);
		eliminar(aux);

	}

}

ConjString::ConjString(const ConjString &otro) {

	tamano = 0;
	listaEnlazada = NULL;
	trie = NULL;
	NodoConjString *p;
	String aux;
	p = otro.listaEnlazada;
	while ( ! (p == NULL) ) {
		aux = p -> elemento;
		p = (p -> siguiente);
		agregar(aux);

	}


}

bool ConjString::vacio() {
	return (listaEnlazada == NULL);
}

int ConjString::dameTamano() {
	return tamano;
}
bool ConjString::pertenece(const String &s1) {

	NodoTrie *p;
	bool retorno;
	String s(s1);
	p = trie;
	retorno = true;
	
	if ( p == NULL ) 

		retorno = false; // si el trie es nulo devuelve falso para cualquier elemento

	

	else {
		
		while (!s.nulo() && retorno)  /* va a bajar en el trie hasta agotar el String */ {

			if (p -> hijos[char2nat(s.primero())] == NULL ) {
				retorno = false; // si no puede seguir devuelve false
			}
			else 
				p = p -> hijos[char2nat(s.primero())];
			s.fin();			
		}		
		if (retorno)
		retorno = p -> fin;

	}
	return retorno;
}

void ConjString::agregar(String &s1) {

	NodoTrie *p;
	String s(s1);
	
	int i;
	NodoConjString *p_nuevoNodo;

	
	if (trie == NULL) {

		trie = new NodoTrie();
		i = 0;

		while ( i < 27) {

			trie -> hijos[i] = NULL;
			i++;
		}


	}

	p = trie;

	i = 0;

	while (!s.nulo()) {
		

		if( p -> hijos[char2nat(s.primero())] == NULL ) {
		
			p -> hijos[char2nat(s.primero())] = new NodoTrie();

			while ( i < 27) {
			
			(p -> hijos[char2nat(s.primero())]) -> hijos[i] = NULL;
			i++;
			}			
			
			p -> hijos[char2nat(s.primero())] -> fin = false;

		}
		p = p -> hijos[char2nat(s.primero())];
		
		s.fin();
		

	}


	if ( p -> fin == false ) { // si no estaba ya el elemento en el conjunto {
		tamano++;
		p -> fin = true;
		// se agrega el elemento en la lista enlazada
		p_nuevoNodo = new NodoConjString();
		p_nuevoNodo -> elemento = s1;
		p_nuevoNodo -> siguiente = listaEnlazada;
		listaEnlazada = p_nuevoNodo;

	}


}


void ConjString::eliminar(const String &s) {

	NodoConjString * i1;
	NodoConjString ** i2;
	bool encontrado, aux;
	NodoTrie *p, **p1;
	String s1(s);
	
	char proxAux, proximo;
	
	
	p = trie;
	encontrado = false;

	p1 = &trie;


	
	while (!s1.nulo() && p != NULL) {


		proxAux = s1.primero();
		/*	Si de este nodo que estoy considerando se desprenden más ramas que aquélla en la que se encontraría el elemento a borrar o bien 
			termina un elemento que se encuentra en el conjunto y no llegué al final del String, guardo el nodo en p1, ya que a partir de aquí
			tendré que borrar los nodos, de ser una rama de ahora en más hasta el ultimo caracter del String.
		*/
		s1.fin();
		if ( p -> fin | hayMasRamas(*p, char2nat(proxAux)) ) {
		
			p1 = &(p -> hijos[char2nat(proxAux)]);
			proximo = proxAux;
			
		}
		p = p -> hijos[char2nat(proxAux)];	


	}
	if (p != NULL) 	{
		if (p -> fin && s1.nulo()) 
			encontrado = true;
			
	}
	// si encontramos el elemento lo eliminamos de la lista y del trie
	

	if (encontrado)	{
	
		// eliminamos el elemento de la lista

		i1 = listaEnlazada;
		i2 = &listaEnlazada;
		encontrado = false;
		while (!encontrado) {
			if (i1 -> elemento == s) { // si encuentra el elemento
				encontrado = true;
				tamano--;
				*i2 = i1 -> siguiente;
				delete i1;
			}
			else {
				i2 = &(i1 -> siguiente);
				i1 = i1 -> siguiente;
			}

		}
		
		
		// eliminamos el elemento del trie
	
		if (esUnaHoja (*p)) {
			
			borrarRama(p1);
		}
		else {
	
		(p -> fin) = false;	
		}
	}	

}

ostream &operator<<(ostream &o, const ConjString &esp){

	NodoConjString *p;
	p = esp.listaEnlazada;
	o << "Elementos del conjunto: ";

	while ( ! (p == NULL) ) {

	o << p -> elemento;
	p = p -> siguiente;
	}
	return o;
	
}

class IteradorConjString {

	public:
		IteradorConjString();
		IteradorConjString(const ConjString &c);
		String proximo();
		bool tieneProximo();
	private:
		NodoConjString *lista;
};

IteradorConjString::IteradorConjString() {
	lista = NULL;
}

IteradorConjString::IteradorConjString(const ConjString &c) {
	
	lista = c.listaEnlazada;


}

String IteradorConjString::proximo() {

	String aux = lista -> elemento;
	lista = lista -> siguiente;
	return aux;


}

bool IteradorConjString::tieneProximo() {
	return lista != NULL;
}

#endif 
